package oop.ex4.crosswords.strategies;

import java.io.File;
import java.lang.reflect.InvocationTargetException;
import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import oop.ex4.crosswords.CrosswordDictionary;
import oop.ex4.crosswords.CrosswordEntry;
import oop.ex4.crosswords.CrosswordPosition;
import oop.ex4.crosswords.EntriesComparator;
import oop.ex4.crosswords.MyCrossword;
import oop.ex4.crosswords.MyCrosswordEntry;
import oop.ex4.crosswords.MyCrossword.CrosswordSquare;
import oop.ex4.search.SearchBoard;

/**
 * This abstract class is used for deciding and performing different crossboard
 * search strategies, it contains methods to be used by those who implant it. 
 * @author yomach
 * @author mbattat
 */
public abstract class CrosswordStrategy implements SearchBoard<CrosswordEntry>{

	///////////////////////////////////////////////////////
	////////////////////////Constants//////////////////////
	///////////////////////////////////////////////////////

	/**
	 * An error message for failure to load strategies.
	 */
	private static final String ERROR_FINDING_STRATEGY = "An error has occured while" +
	" trying to load strategies.";

	///////////////////////////////////////////////////////
	//////////////////////Data Members/////////////////////
	///////////////////////////////////////////////////////

	/**
	 * Holds all of the unused entries sorted by their size & location. 
	 */
	protected EntryList _entriesList;

	/**
	 * The board's current quality.
	 */
	protected int _quality;

	/**
	 * The board's current quality bound.
	 */
	protected int _qualityBound;

	/**
	 * The board's best possible quality.
	 */
	protected int _bestQuality;

	/**
	 * The dictionary.
	 */
	protected ExtendedCrosswordDictionary _dict;

	/**
	 * The board.
	 */
	protected CrosswordSquare[][] _board;

	///////////////////////////////////////////////////////
	//////////////////////Constructors/////////////////////
	///////////////////////////////////////////////////////

	/** 
	 * A constructor that sets the board to the given one.
	 * @param board The board.
	 */
	protected CrosswordStrategy() {
		_entriesList = new EntryList();
		_quality = 0;
	}

	///////////////////////////////////////////////////////
	/////////////////////Public Methods////////////////////
	///////////////////////////////////////////////////////

	@Override
	public void doMove(CrosswordEntry move) {
		CrosswordPosition pos = move.getPosition();
		String term = move.getTerm();
		int x = pos.getX();
		int y = pos.getY();
		boolean vertical = pos.isVertical();
		_quality += term.length();
		_dict.markAsUsed(term);
		_entriesList.markAsUsed(move);
		_board[x][y].setEntry(move);

		// Updates the relevant patterns in the board.
		int length = term.length();
		int startOfWord = (vertical ? y : x);
		int endOfWord = startOfWord + length - 1;
		for (int i = endOfWord; i >= 0; i--) { // Update parallel to the word.
			CrosswordSquare square = _board[(vertical ? x : i)][vertical ? i : y]; 
			if (square == null) { break; }
			for (int j = endOfWord; j >= Math.max(i, startOfWord); j--) {
				square.getCharsAround(vertical).put(j - i, term.charAt(j - endOfWord + length - 1));
			}
		}
		for (int i = endOfWord; i >= startOfWord; i--) { // Update perpendicular to the word.
			for (int j = vertical ? x : y; j >= 0; j--) {
				CrosswordSquare square = _board[(vertical ? j : i)][vertical ? i : j];
				if (square == null) { break; }
				square.getCharsAround(!vertical).put(vertical ? x - j : y - j, term.charAt(i-startOfWord));
			}
		}
	}

	@Override
	public void undoMove(CrosswordEntry move) {
		CrosswordPosition pos = move.getPosition();
		int x = pos.getX();
		int y = pos.getY();
		CrosswordEntry entry = new MyCrosswordEntry(_dict, pos);
		String term = move.getTerm();
		_quality -= term.length();
		_dict.markAsUnused(term);
		_entriesList.markAsUnused(move);
		_board[x][y].setEntry(entry);

		// Updates the relevant patterns in the board.
		boolean parallel = pos.isVertical();
		int length = term.length();
		int startOfWord = (parallel ? y : x);
		int endOfWord = startOfWord + length - 1;
		CharBuffer newPattern = CharBuffer.allocate(term.length());
		CrosswordSquare square;

		for (int i = endOfWord; i >= startOfWord; i--) { // For the entire word that was changed.
			square = _board[(parallel ? x : i)][parallel ? i : y]; 
			if (square == null) { break; }
			if (notPartOfAnExistingTerm(square, parallel)) { // If it's not part of a word, put space and append to new pattern.
				square.getCharsAround(parallel).put(0, ExtendedCrosswordDictionary.SPACE);
				square.getCharsAround(!parallel).put(0, ExtendedCrosswordDictionary.SPACE);
				newPattern.put(length - endOfWord + i - 1, ExtendedCrosswordDictionary.SPACE);
			} else { // Else, append pattern.
				newPattern.put(length - endOfWord + i - 1, square.getCharsAround(!parallel).get(0));
			}
			for (int j = endOfWord - 1; j >= i; j--) { // Fix the rest of the word.
				square.getCharsAround(parallel).put(square.getEntryLength(parallel) - endOfWord + j, newPattern.charAt(length - endOfWord + j));
			}
		}

		for (int i = startOfWord - 1; i >= 0; i--) { // Fix the patterns that are parallel to the removed word. 
			square = _board[(parallel ? x : i)][parallel ? i : y];
			if (square == null) { break; }
			for (int j = startOfWord - i; j <= endOfWord - i; j++) {
				square.getCharsAround(parallel).put(j, newPattern.charAt(j - startOfWord + i));
			}
		}

		for (int i = endOfWord; i >= startOfWord; i--) { // Fix the patterns that are perpendicular to the removed word.
			for (int j = (parallel ? x : y) - 1; j >= 0; j--) {
				square = _board[(parallel ? j : i)][parallel ? i : j];
				if (square == null) { break; }
				square.getCharsAround(!parallel).put(parallel ? x - j : y - j, newPattern.charAt(i-startOfWord));
			}
		}
	}


	@Override
	public int getQuality() {
		return _quality;
	}

	@Override
	public int getQualityBound() {
		return _qualityBound;
	}

	@Override
	public boolean isBestSolution() {
		return _quality == _bestQuality;
	}

	/**
	 * Unsupported!
	 */
	@Override
	public SearchBoard<CrosswordEntry> getCopy() {
		throw new UnsupportedOperationException();
	}

	@Override
	public abstract Iterator<CrosswordEntry> getMoveIterator();

	/**
	 * Returns the strategy's rating for the given board and dictionary. <br>
	 * 0 indicates the strategy does not fit the case while a higher number decides
	 * how good it is for this case.
	 * @param dict The dictionary.
	 * @param board The board.
	 * @return The strategy's rating for the given board and dictionary. Returns   
	 * 0 if the strategy is not good for the board and the strategy's rating otherwise.
	 */
	public abstract int isGoodStrategy(CrosswordDictionary dict,
			CrosswordSquare[][] board);

	/**
	 * Initialize this strategy for the board.
	 * @param dict The dictionary.
	 * @param board The board.
	 */
	public void initializeStrategy(CrosswordDictionary dict, CrosswordSquare[][] board) {
		_board = board;
		_entriesList.loadEntries();
	}

	@Override
	public String toString() {
		String output = "";
		for (int y = 0; y < _board[0].length; y++) {
			for (int x = 0; x < _board.length; x++) {
				if (_board[x][y] == null) { output += " # "; continue; }
				output += " " + _board[x][y].getCharsAround(true).charAt(0) + " ";
			}
			output += "\n";
		}
		return output;
	}

	///////////////////////////////////////////////////////
	//////////////////Public Static Methods////////////////
	///////////////////////////////////////////////////////

	/**
	 * Creates and returns a new operator list based on the operators in the 
	 * package.
	 * @return A new operator list.
	 */
	public static CrosswordStrategy decideStrategy(CrosswordDictionary dict,
			CrosswordSquare[][] board) {
		String pack = CrosswordStrategy.class.getPackage().getName(); // Package name.

		// Get the directory of the strategies.
		File dir = new File(CrosswordStrategy.class.getClassLoader().getResource(pack.replace('.', '/')).getFile());
		File[] files = dir.listFiles(); // Get a list of the strategies.
		int bestStrategyScore = 0;
		CrosswordStrategy bestStrategy = null;
		for (File current : files) {
			try {
				String fileName = pack + "." + current.getName().replace(".class", ""); // Name of operator.
				if (fileName.equals(CrosswordStrategy.class.getName()) 
						|| !fileName.endsWith("Strategy"))  {
					continue; // Ignore this file & every file that doesn't end with "Strategy".
				}
				CrosswordStrategy strategy = (CrosswordStrategy) Class.forName(fileName).getConstructors()[0].newInstance();
				if (strategy.isGoodStrategy(dict, board) > bestStrategyScore) {
					bestStrategy = strategy;
				}
				// If an error is caught then an error message will be printed but it'll attempt to process the next file.
			} catch (IllegalArgumentException e) {
				System.err.println(ERROR_FINDING_STRATEGY);
			} catch (SecurityException e) {
				System.err.println(ERROR_FINDING_STRATEGY);
			} catch (IllegalAccessException e) {
				System.err.println(ERROR_FINDING_STRATEGY);
			} catch (ClassNotFoundException e) {
				System.err.println(ERROR_FINDING_STRATEGY);
			} catch (InstantiationException e) {
				System.err.println(ERROR_FINDING_STRATEGY);
			} catch (InvocationTargetException e) {
				System.err.println(ERROR_FINDING_STRATEGY);	
			}
		}
		if (bestStrategy == null) { throw new NoStrategyFoundException(); }
		return bestStrategy;
	}

	///////////////////////////////////////////////////////
	////////////////////Protected Methods//////////////////
	///////////////////////////////////////////////////////

	/**
	 * Return the number of terms that can fit into an entry, length-wise.
	 * @param board The board.
	 * @return The number of terms that can fit into an entry.
	 */
	protected int getValidTermNum(CrosswordSquare[][] board) {
		int wordNum = 0;
		int longstEntryLength = findLongestEntryLength(board);
		for (String word : _dict.getTerms()) {
			if (word.length() <= longstEntryLength) { 
				wordNum++; 
			}
		}
		return wordNum;
	}

	/**
	 * Return the number of entries that have terms that can fit into it, length-wise.
	 * @param board The board.
	 * @return The number of entries that have terms that can fit into it.
	 */
	protected int getValidEntryNum(CrosswordSquare[][] board) {
		int entryNum = 0;
		int shortestWordLength = _dict.shortestWordLength();
		for (int x = 0; x < board.length; x++) {
			for (int y = 0; y < board[0].length; y++) {
				if (board[x][y] == null) { continue; }
				if (board[x][y].getEntryLength(MyCrossword.VERTICAL) >= shortestWordLength) { // For each entry that we can fit a word into. 
					entryNum++;
				}
				if (board[x][y].getEntryLength(!MyCrossword.VERTICAL) >= shortestWordLength) { // For each entry that we can fit a word into. 
					entryNum++;
				}
			}
		}
		return entryNum;
	}

	///////////////////////////////////////////////////////
	/////////////////////Private Methods///////////////////
	///////////////////////////////////////////////////////

	/**
	 * Checks if the char in the given square is not a part of an existing term 
	 * in the board. <br>
	 * @param square The current square.
	 * @param vertical The direction of the term that this char has been a part of (the
	 * term that had been removed).
	 * @return True if the char in this square is not a part of a term in the board.
	 */
	private boolean notPartOfAnExistingTerm(CrosswordSquare square,
			boolean vertical) {
		CrosswordPosition pos = square.getEntry(vertical).getPosition();
		int x = pos.getX();
		int y = pos.getY(); 
		int endOfWord = (vertical ? y : x);
		CrosswordEntry parallelEntry = null;
		CrosswordEntry perpendicularEntry = null;
		CrosswordSquare currentSquare = null;
		boolean result = false;
		for (int j = endOfWord; j >= 0; j--) {
			currentSquare = _board[(vertical ? x : j)][vertical ? j : y];
			if (currentSquare == null || currentSquare.getCharsAround(vertical).charAt(0) == ExtendedCrosswordDictionary.SPACE) {
				result = true;
				break;
			}
			parallelEntry = currentSquare.getEntry(vertical);
			String currentTerm = parallelEntry.getTerm();
			if (currentTerm != null) {
				result = currentTerm.length() > endOfWord - j ? false : true;
				break;
			}
		}
		if (!result && parallelEntry.getTerm() == null) { result = true; }
		if (!result) { return result; }

		for (int j = (vertical ? x : y); j >= 0; j--) {

			currentSquare = _board[(vertical ? j : endOfWord)][vertical ? endOfWord : j];
			if (currentSquare == null || currentSquare.getCharsAround(!vertical).charAt(0) == ExtendedCrosswordDictionary.SPACE) {
				return true;
			}
			perpendicularEntry = currentSquare.getEntry(!vertical);
			String currentTerm = perpendicularEntry.getTerm();
			if (currentTerm != null) {
				return currentTerm.length() > j - endOfWord ? false : true;
			}
		}
		return true;
	}

	/**
	 * Finds the longest entry in a given board and returns it.
	 * @param board The board.
	 * @return The length of the longest entry in the board.
	 */
	private int findLongestEntryLength(CrosswordSquare[][] board) {
		int longstEntryLength = 0;
		for (int x = 0; x < board.length; x++) {
			for (int y = 0; y < board[0].length; y++) {
				if (board[x][y] == null) { continue; }
				if (board[x][y].getEntryLength(MyCrossword.VERTICAL) > longstEntryLength) { 
					longstEntryLength = board[x][y].getEntryLength(MyCrossword.VERTICAL);
				}
				if (board[x][y].getEntryLength(!MyCrossword.VERTICAL) > longstEntryLength) {
					longstEntryLength = board[x][y].getEntryLength(!MyCrossword.VERTICAL); 
				}
			}
		}
		return longstEntryLength;
	}


	///////////////////////////////////////////////////////
	/////////////////Protected Nested Class////////////////
	///////////////////////////////////////////////////////

	/**
	 * A nested class that holds all available entries in the crossword.
	 * @author yomach
	 * @author mbattat
	 */
	protected class EntryList {

		///////////////////////////////////////////////////////
		//////////////////////Data Members/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * The entry list.
		 */
		private List<SortedSet<CrosswordEntry>> _entries;

		/**
		 * The used entry list.
		 */
		private List<Set<CrosswordEntry>> _usedEntries;


		///////////////////////////////////////////////////////
		//////////////////////Constructors/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Constructs a new entryList.
		 */
		public EntryList() {
			_entries = null;
			_usedEntries = null;
		}

		///////////////////////////////////////////////////////
		/////////////////////Public Methods////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Creates a new list of entries.
		 */
		public void loadEntries() {
			int longestEntry = findLongestEntryLength(_board);
			_entries = new ArrayList<SortedSet<CrosswordEntry>>(longestEntry-1);
			_usedEntries = new ArrayList<Set<CrosswordEntry>>(longestEntry-1);
			for (int i = 0; i < longestEntry-1; i++) {
				_entries.add(i, new TreeSet<CrosswordEntry>(new EntriesComparator()));
				_usedEntries.add(i, new HashSet<CrosswordEntry>());
			}
			for (int x = 0; x < _board.length; x++) {
				for (int y = 0; y < _board[0].length; y++) {
					if (_board[x][y] == null) { continue; }
					if (_board[x][y].getEntryLength(MyCrossword.VERTICAL) > 1) { _entries.get(_board[x][y].getEntryLength(MyCrossword.VERTICAL)-2).add(_board[x][y].getEntry(MyCrossword.VERTICAL)); }
					if (_board[x][y].getEntryLength(!MyCrossword.VERTICAL) > 1) { _entries.get(_board[x][y].getEntryLength(!MyCrossword.VERTICAL)-2).add(_board[x][y].getEntry(!MyCrossword.VERTICAL)); }
				}
			}
		}

		/**
		 * Returns an iterator that iterates over all of the entries in the database
		 * that are at the given length. <br>
		 * The iterator returns them according to the EntriesComparator rules. <br>
		 * The iterator iterate over the original list, so using the iterator remove() method
		 * will remove an item from the list permanently.
		 * Returns null if the length given is out of range.
		 * @param length The length of the entries requested.
		 * @return An iterator that iterates over the entries.
		 * @see EntriesComparator
		 */
		public Iterator<CrosswordEntry> getIterator(int length) {
			if (invalidLength(length)) { return null; }
			return _entries.get(length-2).iterator();
		}

		/**
		 * Returns the list of entries that are at the given length. <br>
		 * The set returned is the original one, any changed imposed on it will affect
		 * the original one.
		 * @param length The length.
		 * @return The list of entries that are at the given length.
		 */
		public SortedSet<CrosswordEntry> getSet(int length) {
			if (invalidLength(length)) { return null; }
			return _entries.get(length-2);
		}

		/**
		 * Returns the length of the longest available entry in the board. <br>
		 * If there are no available entries returns 0.
		 * @return The length of the longest available entry in the board.
		 */
		public int longestEntryLength() {
			for (int i = _entries.size()-1; i >= 0; i--) {
				if (_entries.get(i).size() - _usedEntries.get(i).size() > 0) { return i+2; }
			}
			return 0; // Board is empty. 
		}

		/**
		 * Returns the length of the shortest available entry in the board. <br>
		 * If there are no available entries returns 0.
		 * @return The length of the shortest available entry in the board.
		 */
		public int shortestEntryLength() {
			for (int i = 0; i < _entries.size(); i++) {
				if (_entries.get(i).size() - _usedEntries.get(i).size() > 0) { return i+2; }
			}
			return 0; // Board is empty. 
		}

		/**
		 * Marks an entry as unused.
		 * @param entry The entry.
		 * @return True iff the new entry was successfully marked as unused.
		 */
		public boolean markAsUnused(CrosswordEntry entry) {
			return _usedEntries.get(getEntryLength(entry)-2).remove(getOriginalEntry(entry));
		}

		/**
		 * Marks an entry as used.
		 * @param entry The entry.
		 * @return True iff the entry was successfully marked as used.
		 */
		public boolean markAsUsed(CrosswordEntry entry) {
			return _usedEntries.get(getEntryLength(entry)-2).add(getOriginalEntry(entry));
		}

		/**
		 * Returns all the used entries in the specified length.
		 * @param length The requested entry length.
		 * @return All used entries in the specified length or null if the length
		 * is invalid.
		 */
		public Set<CrosswordEntry> getUsedEntriesSet(int length) {
			if (invalidLength(length)) { return null; }
			return _usedEntries.get(length-2);
		}

		/**
		 * Returns the entry's length.
		 * @param entry The entry.
		 * @return The entry's length.
		 */
		public int getEntryLength(CrosswordEntry entry) {
			CrosswordPosition pos = entry.getPosition();
			return _board[pos.getX()][pos.getY()].getEntryLength(pos.isVertical());
		}

		///////////////////////////////////////////////////////
		////////////////////Private Methods////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Returns true iff the length given is less than 1 or bigger then the size of the list.
		 * @param length The length.
		 * @return true iff the length is outside the bounds.
		 */
		private boolean invalidLength(int length) {
			return (length <= 1 || length > _entries.size()+1);
		}

		/**
		 * Returns the original entry by comparing positions.
		 * @param entry The original entry.
		 * @return The original one.
		 */
		private CrosswordEntry getOriginalEntry(CrosswordEntry entry) {
			CrosswordPosition pos = entry.getPosition();
			int length = _board[pos.getX()][pos.getY()].getEntryLength(pos.isVertical());
			for (CrosswordEntry orgEntry : _entries.get(length-2)) {
				if (orgEntry.equals(entry)) { return orgEntry; }
			}
			return null;
		}
	}

	/**
	 * A nested Iterator that iterate over all possible moves by a specific Strategy.
	 * @author yomach
	 * @author mbattat
	 */
	protected abstract class MovesIterator implements Iterator<CrosswordEntry>{

		///////////////////////////////////////////////////////
		//////////////////////Data Members/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * The next move that this iterator will return.
		 */
		protected CrosswordEntry _nextMove;

		/**
		 * Holds the length of the shortest term in the crossword.
		 */
		protected final int _minFit;

		/**
		 * Holds the length of the longest entry in the dictionary.
		 */
		protected final int _maxFit;

		///////////////////////////////////////////////////////
		//////////////////////Constructors/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Constructs a new MoveIterator in a certain strategy.
		 */
		public MovesIterator () {
			_minFit = _dict.shortestWordLength();
			_maxFit = _entriesList.longestEntryLength();
		}

		///////////////////////////////////////////////////////
		/////////////////////Public Methods////////////////////
		///////////////////////////////////////////////////////

		@Override
		public boolean hasNext() {
			if (_nextMove == null) { _nextMove = createNextMove(); }
			return _nextMove != null; 
		}

		@Override
		public CrosswordEntry next() {
			if (_nextMove == null) { throw new NoSuchElementException(); }
			CrosswordEntry move = _nextMove;
			_nextMove = null;
			return move;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}

		///////////////////////////////////////////////////////
		////////////////////Private Methods////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Creates the next move for the iterator to fit the strategy. 
		 * @return The next move.
		 */
		protected abstract CrosswordEntry createNextMove();

	}
}	